package com.cty._03_SolutionSeekingMindset._36_ConvertBinarySearchTree;

/**
 * @Auther: cty
 * @Date: 2020/7/14 8:35
 * @Description: 面试题36：二叉搜索树与双向链表
 * 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求
 * 不能创建任何新的结点，只能调整树中结点指针的指向。
 * @version: 1.0
 */
public class ConvertBinarySearchTree {

    private static BinaryTreeNode lastNode = null;

    public static BinaryTreeNode convert(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return null;

        BinaryTreeNode listHead = treeRoot;
        while(listHead.leftChild != null)
            listHead = listHead.leftChild;

        recConvert(treeRoot);

        return listHead;
    }  // end convert

    private static void recConvert(BinaryTreeNode treeRoot){
        if(treeRoot == null)  // 递归结束条件
            return;
        BinaryTreeNode current = treeRoot;

        if(current.leftChild != null)
            recConvert(current.leftChild);

        current.leftChild = lastNode;
        if(lastNode != null)
            lastNode.rightChild = current;
        lastNode = current;

        if(current.rightChild != null)
            recConvert(current.rightChild);
    }  // end recConvert

}  // end class

class BinaryTreeNode{
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){};

    public BinaryTreeNode(int value){this.value = value;};
}  // end class